package leetcode_500;

/**
 *@author 周杨
 *OnesAndZeroes_474 给定一个字符串数组 再给定能取0和1的数字
 *describe:理论上用动归能在O(n)时间复杂度内完成   AC 73%
 *2018年8月30日 下午12:24:24
 */
public class OnesAndZeroes_474_ {
	
	/**
	 * describe:完美解 动态规划 前提是m和n均不能太大 
	 * dp[i][j]当前剩余i和j时的最完美方案
	 * 2018年8月30日 下午12:24:09
	 */
	public int findMaxForm(String[] strs, int m, int n) {
		   if(strs.length==0)
			   return 0;
		   int dp[][]=new int[m+1][n+1];
		   for(String str:strs) {
			   int zero=0,one=0;
			   for(int i=0;i<str.length();++i) {
				   if(str.charAt(i)=='0')
					   ++zero;
				   else
					   ++one;
			   }
			  for(int i=m;i>=zero;--i)
				  for(int j=n;j>=one;--j)
					  dp[i][j]=Math.max(dp[i][j], dp[i-zero][j-one]+1);
			  //是不要这个好 还是要了好 判断两者备忘录
		   }
		   return dp[m][n];
		   
	 }
	
	
	 int max=0;
	 /**
	 * describe:直接深搜 超时
	 * 2018年8月30日 下午12:02:18
	 */
	public int findMaxForm1(String[] strs, int m, int n) {
		   int dp0[]=new int[strs.length];
		   int dp1[]=new int[strs.length];
	       for(int i=0;i<strs.length;++i) {
	    	   int [] res=count(strs[i]);
	    	   dp0[i]=res[0];
	    	   dp1[i]=res[1];
	       }
	       dfs(dp0,dp1,m,n,0,0);
	       return this.max;
	 }
	 
	 private void dfs(int[]dp0,int[]dp1,int left0,int left1,int nowCount,int index) {
		 if(index==dp0.length||left0==0&&left1==0)
			 return ;
		 if(left0>=dp0[index]&&left1>=dp1[index]) {
			 this.max=Math.max(this.max, nowCount+1);//就选这件
			 dfs(dp0,dp1,left0-dp0[index],left1-dp1[index],nowCount+1,index+1);
		 }
		 dfs(dp0,dp1,left0,left1,nowCount,index+1);//不选
	 }
	 
	 private int[] count(String str) {
		 int res0=0,res1=0;
		 for(int i=0;i<str.length();++i) {
			 if('0'==str.charAt(i))
				 res0++;
			 else
				 res1++;
		 }
		 return new int[] {res0,res1};
	 }
}
